/**
 * https://leetcode.cn/problems/minimum-height-trees/submissions/
 * 310.最小高度树
 * medium 陈贝纯 2024.11.24
 * dfs
 */


class Solution {
public:
    int findlong(int x,vector<int>&parent,vector<vector<int>>& adj){
        int n=adj.size();
        queue<int> q;
        vector<bool> v(n,true);
        q.push(x);
        v[x]=false;
        int node=-1;
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            node=cur;
            for(auto num:adj[cur]){
                if(v[num]){
                    v[num]=false;
                    parent[num]=cur;
                    q.push(num);
                }
            }
        }
        return node;
    }
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n==1)
            return {0};
        vector<vector<int>> adj(n);
        for(auto num:edges){
            adj[num[0]].push_back(num[1]);
            adj[num[1]].push_back(num[0]);
        }
        vector<int> parent(n,-1);
        int x=findlong(0,parent,adj);
        int y=findlong(x,parent,adj);
        vector<int> path;
        parent[x]=-1;
        while(y!=-1){
            path.push_back(y);
            y=parent[y];
        }
        int m=path.size();
        if(m%2==0){
            return {path[m/2-1],path[m/2]};
        }else
        return {path[m/2]};
    }
};